package HashTab;

import java.util.Scanner;

public class HashTabDemo {
	public static void main(String[] args) {
		//创建一个 哈希表
		HashTab hashTab = new HashTab(7);

		String key = "";
		Scanner scanner = new Scanner(System.in);
		while (true) {
			System.out.println("add:添加");
			System.out.println("list:显示");
			System.out.println("find:查找");
			System.out.println("del:删除");
			System.out.println("exit:退出");

			key = scanner.next();
			switch (key) {
				case "add":
					System.out.println("id");
					int id = scanner.nextInt();
					System.out.println("name");
					String name = scanner.next();
					Emp emp = new Emp(id, name);
					hashTab.add(emp);
					break;
				case "list":
					hashTab.list();
					break;
				case "find":
					System.out.println("id");
					id = scanner.nextInt();
					hashTab.findEmpById(id);
					break;
				case "del":
					System.out.println("id");
					id = scanner.nextInt();
					hashTab.deleteById(id);
					break;
				case "exit":
					scanner.close();
					break;
			}
		}
	}
}

//创建哈希表
class HashTab {
	private EmpLinkedList[] empLinkedLists;
	private int size;//表示共有多少条

	//构造器
	public HashTab(int size) {
		this.size = size;
		//初始化 empLinkedLists
		empLinkedLists = new EmpLinkedList[size];
		//分别初始化每一条链表
		for (int i = 0; i < size; i++) {
			empLinkedLists[i] = new EmpLinkedList();
		}
	}

	//添加雇员
	public void add(Emp emp) {
		//根据员工的 id ，得到该员工应该加入的链表
		int empLinkedListsNo = hashFun(emp.id);
		//将 emp 加入到对应的链表中
		empLinkedLists[empLinkedListsNo].add(emp);
	}

	//编写散列函数，使用一个简单取模法
	public int hashFun(int id) {
		return id % size;
	}

	//遍历
	public void list() {
		for (int i = 0; i < size; i++) {
			empLinkedLists[i].list(i);
		}
	}


	//根据 id 查找
	public void findEmpById(int id) {
		//根据散列表函数 确定在那一条链表
		int empLinkedListsNo = hashFun(id);
		Emp emp = empLinkedLists[empLinkedListsNo].findEmpById(id);
		if (emp != null) {
			//找到了
			System.out.printf("在第%d条链表中 找到 雇员 id = %d\n", empLinkedListsNo + 1, id);
		} else {
			System.out.println("没找到");
		}
	}

	//删除
	public void deleteById(int id) {
		int empLinkedListsNo = hashFun(id);
		if (empLinkedLists[empLinkedListsNo].deleteByid(id)) {
			System.out.println("成功");
		} else {
			System.out.println("失败");
		}
	}
}

//表示一个雇员类
class Emp {
	public int id;
	public String name;
	public Emp next;

	public Emp(int id, String name) {
		super();
		this.id = id;
		this.name = name;
	}
}

//创建一个 EmpLinkedList 表示一个链表
class EmpLinkedList {
	//头指针，指向第一个 Emp，因此我们这个链表的 head
	private Emp head;//默认 null

	//添加雇员
	//假定添加雇员时， id 时自增的，即id总是从小到大
	//因此将该雇员，加入到最后
	public void add(Emp emp) {
		//如果添加第一个员工
		if (head == null) {
			//说明添加第一个
			head = emp;
			return;
		}
		//如果不是第一个，定位到最后
		Emp curEmp = head;
		while (true) {
			if (curEmp.next == null) {
				break;
			}
			curEmp = curEmp.next;//后移
		}
		//退出时直接加到最后
		curEmp.next = emp;
	}

	//遍历
	public void list(int no) {
		if (head == null) {
			//链表为空，不用继续
			System.out.println("链表" + (no + 1) + "为空");
			return;
		}
		System.out.println("链表" + (no + 1) + "信息");
		Emp curEmp = head;
		while (true) {
			System.out.printf("id = %d ; name = %s\t", curEmp.id, curEmp.name);
			if (curEmp.next == null) {
				//遍历到最后，退出
				break;
			}
			curEmp = curEmp.next;//后移

		}
		System.out.println("\n");
	}

	//根据 id 查找
	public Emp findEmpById(int id) {
		//判断是否为空
		if (head == null) {
			System.out.println("链表为空");
			return null;
		}
		Emp curEmp = head;
		while (true) {
			if (curEmp.id == id) {
				//找到
				break;
			}
			//退出条件
			if (curEmp.next == null) {
				//没有找到
				curEmp = null;
				break;
			}
			curEmp = curEmp.next;
		}
		return curEmp;
	}

	//根据 id 删除
	public boolean deleteByid(int id) {
		if (head == null) {
			System.out.println("链表为空");
			return false;
		}
		Emp empCur = head;
		Emp empPre = head;
		int index = 1;
		while (true) {
			if (empCur.id == id) {
				break;
			}
			if (empCur.next == null) {
				System.out.println("不存在");
				return false;
			}
			index = 2;
			empPre = empCur;
			empCur = empCur.next;
		}
		if (index == 1) {
			head = empCur.next;
		} else if (index == 2) {
			empPre.next = empCur.next;
		}
		return true;

	}
}
